package offer.day29;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No48LongestSubStringWithoutDuplication {
    /*
     * 面试题48：最长不含重复字符的子字符串+长度
     * 题目：请从字符串中找出一个最长的不包含重复自负的子字符串，计算该子字符串的长度。
     * 假设字符串中只包含'a'~'z'的字符。
     * 例如，在字符串"arabcacfr"中，最长的不含重复字符的子字符串是"acfr",长度为4
     *
     * 思路：运用动态规划的思想进行解题，设定f(i)表示以第i格字符串为结尾的不包含重复自负的子字符串的最长长度。
     * 从左到右逐一扫描字符串中的每一个字符，其中
     * 当第i个字符之前没有出现过，则f(i) = f(i-1)+1
     * 当第i个字符之前出现过，首先计算第i个字符和它上次出现的字符串中的位置的距离，记为d，则分为两种情况：
     * 	若d小于等于f(i-1),此时重复的字符出现在f(i-1)对应的最长字符串中，因此f(i) = d
     *	若d大于f(i-1),此时重复的字符出现在f(i-1)的前面，不在f(i-1)对应的字符串中，因此不必考虑对f(i)的影响，因此f(i) = f(i-1)+1
     * */
    static String[] str;

    public static void main(String[] args) {


        String s = "arabcacfr";

        System.out.println("字符串中最长的不含重复的子字符串长度是" + LongestSubStringWithoutDuplication(s));

        System.out.println("其子字符串为" + Arrays.toString(str));
    }

    private static int LongestSubStringWithoutDuplication(String s) {
        if (s == null || s.length() == 0) return -1;
        int[] position = new int[26];
        for (int i = 0; i < 26; i++) {
            position[i] = -1;
        }
        int[] dp = new int[s.length() + 1];
        dp[0] = 0;
        for (int i = 0; i < s.length(); i++) {
            int preIndex = position[s.charAt(i) - 'a'];
            if (preIndex == -1) {
                position[s.charAt(i) - 'a'] = i;
                dp[i + 1] = dp[i] + 1;
            } else {
                int dis = i - preIndex;
                if (dis > dp[i]) {
                    dp[i + 1] = dp[i] + 1;
                } else {
                    dp[i + 1] = i - preIndex;
                    position[s.charAt(i) - 'a'] = i;
                }
            }
        }
        int[] res = Arrays.copyOfRange(dp, 1, dp.length);

        List<Integer> maxIndexArray = new ArrayList<>();
        int maxIndex = 0;
        for (int i = 1; i < res.length; i++) {
            if (res[i] > res[i - 1]) {
                maxIndex = i;
            }
        }
        for (int i=0;i<res.length;i++) {
            if (res[i] == res[maxIndex]) {
                maxIndexArray.add(i);
            }
        }
        str = new String[maxIndexArray.size()];
        for (int i = 0; i < str.length; i++) {
            int index = maxIndexArray.get(i);
            str[i] = s.substring(index - res[index]+1, index+1);
        }
        System.out.println(maxIndexArray);
        return res[maxIndex];
    }
}
